# 最大公约数(没有更优解的答案)
import math


def count_gcd_bf(a, b, c, d, k):
    """暴力法"""
    cnt = 0
    start_a, start_c = a, c
    while start_a % k != 0:
        start_a += 1
    while start_c % k != 0:
        start_c += 1
    for i in range(start_a, b + 1, k):
        for j in range(start_c, d + 1, k):
            if math.gcd(i, j) == k:
                cnt += 1
    return cnt


def count_gcd_opt(a, b, c, d, k):
    """问题转换：将 x 和 y 都除以 k，转化为求 gcd(x', y')= 1 其中 x' 和 y' 分别是 x/k 和 y/k
    预处理莫比乌斯函数：使用欧拉筛预处理较小范围的莫比乌斯函数。
    数论分块：分块处理大范围的情况，结合前缀和快速计算贡献。"""
    def compute_mobius(maxd):
        if maxd < 1:
            return []
        mob = [1] * (maxd + 1)
        is_prime = [True] * (maxd + 1)
        for p in range(2, maxd + 1):
            if is_prime[p]:
                mob[p] = -1
                for multiple in range(2 * p, maxd + 1, p):
                    is_prime[multiple] = False
                    mob[multiple] *= -1
                p_square = p * p
                for multiple in range(p_square, maxd + 1, p_square):
                    mob[multiple] = 0
        return mob

    if k == 0:
        count_x = 1 if a <= 0 <= b else 0
        count_y = 1 if c <= 0 <= d else 0
        return count_x * count_y

    x1 = (a + k - 1) // k
    x2 = b // k
    y1 = (c + k - 1) // k
    y2 = d // k

    if x1 > x2 or y1 > y2:
        return 0

    maxd = max(x2, y2)
    mob = compute_mobius(maxd)
    total = 0

    for d in range(1, maxd + 1):
        if mob[d] == 0:
            continue
        cnt_x = x2 // d - (x1 - 1) // d
        cnt_y = y2 // d - (y1 - 1) // d
        total += mob[d] * cnt_x * cnt_y

    return total


if __name__ == '__main__':
    print(count_gcd_bf(2, 5, 1, 5, 1))
    print(count_gcd_bf(1, 5, 1, 5, 2))
    print(count_gcd_opt(1, 5, 1, 5, 2))
